/**
 * Created with IntelliJ IDEA.
 * Description: lettcode: 897. 递增顺序搜索树
 * <a href="https://leetcode.cn/problems/increasing-order-search-tree/">...</a>
 * User: DELL
 * Date: 2023-08-26
 * Time: 22:36
 */

class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode() {}
    public TreeNode(int val) { this.val = val; }
    public TreeNode(int val, TreeNode left, TreeNode right) {
       this.val = val;
       this.left = left;
       this.right = right;
   }
}

public class Solution {
    /**
     * 解题思路:
     * 总体思路就是通过一个全局变量 preNode 来记录上一个遍历的结点,
     * 然后在中序遍历的时候,通过修改前一个结点和当前结点的左右孩子结点
     * 的引用来改变当前树的结构.
     * 本题右以下两点需要注意:
     * 1. 使用一个 newNode 来记录修改后的树的根节点,类似于无头链表的
     *    头结点的作用.
     * 2. 在改变树的结构时要注意将当前结点的左孩子结点设为 null,否则可能
     *    会出现环.
     */
    private TreeNode preNode = null;
    public TreeNode increasingBST(TreeNode root) {
        TreeNode newNode = new TreeNode(-1);
        preNode = newNode;
        inOrder(root);
        preNode = null;
        return newNode.right;
    }

    private void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        // 左子树
        inOrder(root.left);
        // 处理
        // 错误的代码如下,这样子处理可能会使得最后一个节点的左结点没有改为null而形成环
        // 可能出现错误的情况已经放在main方法中了
//        preNode.left = null;
//        preNode.right = root;
//        preNode = root;
        // 正确的代码如下
        preNode.right = root;
        root.left = null;
        preNode = root;
        // 右子树
        inOrder(root.right);
    }

    public static void main(String[] args) {
        // 这种情况下的树最后会出现环
        TreeNode node = new TreeNode(2);
        node.left = new TreeNode(1);
        node.right = new TreeNode(4);
        node.right.left = new TreeNode(3);
        Solution solution = new Solution();
        solution.increasingBST(node);
    }
}